Karnaugh map

An example Karnaugh map

The Karnaugh map (K-map for short), Maurice Karnaugh's 1953 refinement of Edward Veitch's 1952 Veitch diagram, is a method to simplify Boolean algebra expressions. The Karnaugh map reduces the need for extensive calculations by taking advantage of humans' pattern-recognition capability, permitting the rapid identification and elimination of potential race conditions.

In a Karnaugh map the boolean variables are transferred (generally from a truth table) and ordered according to the principles of Gray code in which only one variable changes in between squares. Once the table is generated and the output possibilities are transcribed, the data is arranged into the largest possible groups containing 2ⁿ cells (n=0,1,2,3...)^[1] and the minterm is generated through the axiom laws of boolean algebra.

History

The Karnaugh map was invented in 1952 by Edward W. Veitch and developed further in 1953 by Maurice Karnaugh, a telecommunications engineer at Bell Labs.

Properties

A four variable minterm Karnaugh map. Note: the four boolean variables A, B, C, and D. The top side of the grid the first "0" represents the possibility of the input NOT A, the second "0" represents NOT B, a "1" represents A, and so forth. There are sixteen permutations out of the four variables, and thus sixteen possible outputs.

Purpose

Normally, extensive calculations are required to obtain the minimal expression of a Boolean function, however Karnaugh mapping reduces the need for such calculations by:

Taking advantage of the human brain's pattern-matching capability to decide which terms should be combined to obtain the simplest expression.
Permitting the rapid identification and elimination of potential race hazards, which is unavoidable in boolean equations.
Providing an excellent aid for simplification of up to six variables, however with more variables it becomes more difficult to discern optimal patterns.
Helping to teach about Boolean functions and minimization.
For problems involving more than six variables, solving the boolean expressions is preferred over the use of a Karnaugh mapping.

Problems

Karnaugh maps generally become more cluttered and hard to interpret when adding more variables. A general rule is that Karnaugh maps work well for up to four variables, and shouldn't be used at all for more than six variables. For expressions with larger numbers of variables, the Quine–McCluskey algorithm can be used. Nowadays in general the minimization process is carried out by computer, for which the Espresso heuristic logic minimizer has become the standard minimization program.

Procedures

The K-Map method may theoretically be applied for the simplification of any boolean expression regardless of its number of variables, but is most often used when there are fewer than six variables because K-Maps of expressions with more than six variables are complex and tedious to simplify. Each variable contributes two possibilities: the initial value, and its inverse; it therefore organizes all possibilities of the system. The variables are arranged in Gray code in which only one variable changes between two adjacent grid boxes.

Once the variables have been defined, the output possibilities are transcribed according to the grid location provided by the variables. Thus for every possibility of a boolean input or variable the output possibility is defined.

When the Karnaugh map has been completed, to derive a minimized function the "1s" or desired outputs are grouped into the largest possible rectangular groups in which the number of grid boxes (output possibilities) in the groups must be equal to a power of 2.^[1] For example, the groups may be 4 boxes in a line, 2 boxes high by 4 boxes long, 2 boxes by 2 boxes, and so on. "Don't care(s)" possibilities (generally represented by a "X") are grouped only if the group created is larger than the group with "Don't care" is excluded. The boxes can be used more than once only if it generates the least number of groups. Each "1" or desired output possibilities must be contained within at least one grouping.

The groups generated are then converted to a boolean expression by: locating and transcribing the variable possibility attributed to the box, and by the axiom laws of boolean algebra—in which if the (initial) variable possibility and its inverse are contained within the same group the variable term is removed. Each group provides a "product" to create a "sum-of-products" in the boolean expression.

To determine the inverse of the Karnaugh map, the "0s" are grouped instead of the "1s". The two expressions are non-complementary.

Relationships

4 set Venn diagram with numbers (0-15) and set names (A-D) matching above minterm diagram

Each square in a Karnaugh map corresponds to a minterm (and maxterm). The picture to the right shows the location of each minterm on the map. A Venn diagram of four sets—labeled A, B, C, and D—is shown to the right that corresponds to the 4-variable K-map of minterms just above it:

Variable A of the K-map corresponds set A in the Venn diagram; etc.
Minterm m0 of the K-map corresponds to area 0 in the Venn diagram; etc.
Minterm m9 is ABCD (or 1001) in the K-map corresponds only to where sets A & D intersect in the Venn diagram.

Thus, a specific minterm identifies a unique intersection of all four sets. The Venn diagram can include an infinite number of sets and still correspond to the respective Karnaugh maps. With increasing number of sets and variables, both Venn diagram and Karnaugh map increase in complexity to draw and manage.

Toroidally connected

The grid is toroidally connected, so the rectangular groups can wrap around edges. For example m9 can be grouped with m1; just as m0, m8, m2, and m10 can be combined into a two-by-two group.

Size of map

The size of the Karnaugh map with n Boolean variables is determined by 2ⁿ. The size of the group within a Karnaugh map with n Boolean variables and k number of terms in the resulting Boolean expression is determined by 2^nk. Common sized maps are of 2 variables which is a 2×2 map, 3 variables which is a 2×4 map, and 4 variables which is a 4×4 map.

2-variable k-map

3-variable k-map

4-variable k-map

Example

Karnaugh maps are used to facilitate the simplification of Boolean algebra functions. The following is an unsimplified Boolean Algebra function with Boolean variables $A$ , $B$ , $C$ , $D$ , and their inverses. They can be represented in two different functions:

$f(A, B, C, D) = \sum_{}(6, 8, 9, 10, 11, 12, 13, 14)$ Note: The values inside $\sum_{}$ are the minterms to map (i.e. which rows have output 1 in the truth table).
$f(A, B, C, D) = (\overline{A}BC\overline{D}) + (A\overline{B}\overline{C}\overline{D}) + (A\overline{B}\overline{C}D) + (A\overline{B}C\overline{D}) + (A\overline{B}CD) + (AB\overline{C}\overline{D}) + (AB\overline{C}D) + (ABC\overline{D})$

Truth table

Using the defined minterms, the truth table can be created:

#	$A$	$B$	$C$	$D$	$f(A, B, C, D)$
0	0	0	0	0	0
1	0	0	0	1	0
2	0	0	1	0	0
3	0	0	1	1	0
4	0	1	0	0	0
5	0	1	0	1	0
6	0	1	1	0	1
7	0	1	1	1	0
8	1	0	0	0	1
9	1	0	0	1	1
10	1	0	1	0	1
11	1	0	1	1	1
12	1	1	0	0	1
13	1	1	0	1	1
14	1	1	1	0	1
15	1	1	1	1	0

Karnaugh map

K-map showing minterms and boxes covering the desired minterms. The brown region is an overlapping of the red (square) and green regions.

The input variables can be combined in 16 different ways, so the Karnaugh map has 16 positions, and therefore is arranged in a 4 × 4 grid.

The binary digits in the map represent the function's output for any given combination of inputs. So 0 is written in the upper leftmost corner of the map because ƒ = 0 when A = 0, B = 0, C = 0, D = 0. Similarly we mark the bottom right corner as 1 because A = 1, B = 0, C = 1, D = 0 gives ƒ = 1. Note that the values are ordered in a Gray code, so that precisely one variable changes between any pair of adjacent cells.

After the Karnaugh map has been constructed the next task is to find the minimal terms to use in the final expression. These terms are found by encircling groups of 1s in the map. The groups must be rectangular and must have an area that is a power of two (i.e. 1, 2, 4, 8…). The rectangles should be as large as possible without containing any 0s. The optimal groupings in this map are marked by the green, red and blue lines. Note that groups may overlap. In this example, the red and green groups overlap. The red group is a 2 × 2 square, the green group is a 4 × 1 rectangle, and the overlap area is indicated in brown.

The grid is toroidally connected, which means that the rectangular groups can wrap around edges, so $\scriptstyle A\overline{D}$ is a valid term, although not part of the minimal set—this covers Minterms 8, 10, 12, and 14.

Perhaps the hardest-to-visualize wrap-around term is $\scriptstyle\overline{B}\,\overline{D}$ which covers the four corners—this covers minterms 0, 2, 8, 10.

Solution

Once the Karnaugh Map has been constructed and the groups derived, the solution can be found by eliminating extra variables within groups using the axiom laws of boolean algebra. It can be implied that rather than eliminating the variables that change within a grouping, the minimal function can be derived by noting which variables stay the same.

For the Red grouping:

The variable $A$ maintains the same state (1) in the whole encircling, therefore it should be included in the term for the red encircling.
Variable $B$ does not maintain the same state (it shifts from 1 to 0), and should therefore be excluded.
$C$ does not change: it is always 0. Because $C$ is 0, it has to be negated before it is included (thus, $\overline{C}$ ).
$D$ changes, so it is excluded as well.

Thus the first term in the Boolean sum-of-products expression is $A\overline{C}.$

For the Green grouping we see that $A$ and $B$ maintain the same state, but $C$ and $D$ change. $B$ is 0 and has to be negated before it can be included. Thus the second term is $A\overline{B}.$

In the same way, the Blue grouping gives the term $BC\overline{D}.$

The solutions of each grouping are combined into: $A\overline{C} + A\overline{B} + BC\overline{D}.$

Inverse

The inverse of a function is solved in the same way by grouping the 0s instead.

The three terms to cover the inverse are all shown with grey boxes with different colored borders:

brown— $\overline{A}\,\overline{B}$
gold— $\overline{A}\,\overline{C}$
blue— $BCD$

This yields the inverse:

$\overline{F} = \overline{A}\,\overline{B} + \overline{A}\,\overline{C} + BCD$

Through the use of De Morgan's laws, the product of sums can be determined:

$\overline{\overline{F}} = \overline{ \overline{A}\,\overline{B} + \overline{A}\,\overline{C} + BCD }$

$F = \left(A + B\right)\left(A + C\right)\left(\overline{B} + \overline{C} + \overline{D}\right)$

Don't cares

The minterm 15 is dropped and replaced as a don't care, this removes the green term completely but restricts the blue inverse term

Karnaugh maps also allow easy minimizations of functions whose truth tables include "don't care" conditions (that is, sets of inputs for which the designer doesn't care what the output is) because "don't care" conditions can be included in a ring to make it larger. They are usually indicated on the map with a dash or X.

The example to the right is the same above example but with minterm 15 dropped and replaced as a don't care. This allows the red term to expand all the way down and, thus, removes the green term completely.

This yields the new minimum equation:

$F = A + BC\overline{D}.$

Note that the first term is just $A$ not $A\overline{C}$ . In this case, the don't care has dropped a term (the green); simplified another (the red); and removed the race hazard (the yellow as shown in a following section).

Also, since the inverse case no longer has to cover minterm 15, minterm 7 can be covered with $\left(A + \overline{D}\right)$ rather than $\left(\overline{B} + \overline{C} + \overline{D}\right)$ with similar gains.

Race hazards

Elimination

Above k-map with the $A\overline{D}$ term added to avoid race hazards

Karnaugh maps are useful for detecting and eliminating race hazards. They are very easy to spot using a Karnaugh map, because a race condition may exist when moving between any pair of adjacent, but disjointed, regions circled on the map.

In the above example, a potential race condition exists when C is 1 and D is 0, A is 1, and B changes from 1 to 0 (moving from the blue state to the green state). For this case, the output is defined to remain unchanged at 1, but because this transition is not covered by a specific term in the equation, a potential for a glitch (a momentary transition of the output to 0) exists.
There is a second glitch in the same example that is more difficult to spot: when D is 0 and A and B are both 1, with C changing from 1 to 0 (moving from the blue state to the red state). In this case the glitch wraps around from the top of the map to the bottom.

Whether these glitches do occur depends on the physical nature of the implementation, and whether we need to worry about it depends on the application.

In this case, an additional term of $A\overline{D}$ would eliminate the potential race hazard, bridging between the green and blue output states or blue and red output states: this is shown as the yellow region.

The term is redundant in terms of the static logic of the system, but such redundant, or consensus terms, are often needed to assure race-free dynamic performance.

Similarly, an additional term of $\overline{A}D$ must be added to the inverse to eliminate another potential race hazard. Applying De Morgan's laws creates another product of sums expression for F, but with a new factor of $\left(A + \overline{D}\right)$ .

2-variable map examples

The following are all the possible 2-variable, 2 × 2 Karnaugh maps. Listed with each is the minterms as a function of $\sum_{}$ () and the race hazard free (see previous section) minimum equation.

$\sum_{}$ (0); K = 0	$\sum_{}$ (1); K = A′B′	$\sum_{}$ (2); K = AB′	$\sum_{}$ (3); K = A′B
$\sum_{}$ (4); K = AB	$\sum_{}$ (1,2); K = B′	$\sum_{}$ (1,3); K = A′	$\sum_{}$ (1,4); K = A′B′ + AB
$\sum_{}$ (2,3); K = AB′ + A′B	$\sum_{}$ (2,4); K = A	$\sum_{}$ (3,4); K = B	$\sum_{}$ (1,2,3); K = A′ + B′
$\sum_{}$ (1,2,4); K = A + B′	$\sum_{}$ (1,3,4); K = A′ + B	$\sum_{}$ (2,3,4); K = A + B	$\sum_{}$ (1,2,3,4); K = 1

References

↑ ^1.0 ^1.1 "Karnaugh Maps - Rules of Simplification". http://www.ee.surrey.ac.uk/Projects/Labview/minimisation/karrules.html. Retrieved 2009-05-30.

External links

Detect Overlapping Rectangles, by Herbert Glarner.
Using Karnaugh maps in practical applications, Circuit design project to control traffic lights.
Karnaugh Map Example
Minimization of Boolean Functions
Kmap minimizer Online Flash application, published 2009.
Boolean Function Simplification Software, freeware application for the Palm OS.
GKMap, free software application at SourceForge.net.
GPA141, Java applet for solving 5-variable Karnaugh maps available only in French.
Karnaugh Map Minimizer, free software application at SourceForge.net.
Karnaugh map minimization software, freeware application available in English, Czech, and German.
Karma 3, A set of logic synthesis tools including Karnaugh maps, Quine-McCluskey minimization, BDDs, probabilities, teaching module and more. Logic Circuits Synthesis Labs (LogiCS) - UFRGS, Brazil.
Karnaugh Map Explorer 1.0, JavaScript application.

Karnaugh map

Contents

History

Properties

Purpose

Problems

Procedures

Relationships

Toroidally connected

Size of map

Example

Truth table

Karnaugh map

Solution

Inverse

Don't cares

Race hazards

Elimination

2-variable map examples

See also

References

Further reading

External links

#	$A$	$B$	$C$	$D$	$f(A, B, C, D)$
0	0	0	0	0	0
1	0	0	0	1	0
2	0	0	1	0	0
3	0	0	1	1	0
4	0	1	0	0	0
5	0	1	0	1	0
6	0	1	1	0	1
7	0	1	1	1	0
8	1	0	0	0	1
9	1	0	0	1	1
10	1	0	1	0	1
11	1	0	1	1	1
12	1	1	0	0	1
13	1	1	0	1	1
14	1	1	1	0	1
15	1	1	1	1	0

#	$A$	$B$	$C$	$D$	$f(A, B, C, D)$
0	0	0	0	0	0
1	0	0	0	1	0
2	0	0	1	0	0
3	0	0	1	1	0
4	0	1	0	0	0
5	0	1	0	1	0
6	0	1	1	0	1
7	0	1	1	1	0
8	1	0	0	0	1
9	1	0	0	1	1
10	1	0	1	0	1
11	1	0	1	1	1
12	1	1	0	0	1
13	1	1	0	1	1
14	1	1	1	0	1
15	1	1	1	1	0

#	$A$	$B$	$C$	$D$	$f(A, B, C, D)$
0	0	0	0	0	0
1	0	0	0	1	0
2	0	0	1	0	0
3	0	0	1	1	0
4	0	1	0	0	0
5	0	1	0	1	0
6	0	1	1	0	1
7	0	1	1	1	0
8	1	0	0	0	1
9	1	0	0	1	1
10	1	0	1	0	1
11	1	0	1	1	1
12	1	1	0	0	1
13	1	1	0	1	1
14	1	1	1	0	1
15	1	1	1	1	0